package solutions.leetcode.hard;

/**
 * @author lzd
 * <a href="https://leetcode.cn/problems/number-of-distinct-roll-sequences/">2318. 不同骰子序列的数目</a>
 */
public class Solution2318 {
    // 动态规划
    public int distinctSequences(int n) {
        if (n == 1) {
            return 6;
        }
        int mod = 1000000007;
        int[][] stepArray = {
                {0, 1, 1, 1, 1, 1},
                {1, 0, 1, 0, 1, 0},
                {1, 1, 0, 1, 1, 0},
                {1, 0, 1, 0, 1, 0},
                {1, 1, 1, 1, 0, 1},
                {1, 0, 0, 0, 1, 0}
        };
        int[][] tArray1 = {
                {0, 1, 1, 1, 1, 1},
                {1, 0, 1, 0, 1, 0},
                {1, 1, 0, 1, 1, 0},
                {1, 0, 1, 0, 1, 0},
                {1, 1, 1, 1, 0, 1},
                {1, 0, 0, 0, 1, 0}
        };
        int[][] tArray2 = new int[6][6];
        int[][] resultArray = tArray1;
        int[][] targetArray = tArray2;

        int ind = n;
        while (ind-- > 2) {
            int[][] t = resultArray;
            resultArray = targetArray;
            targetArray = t;
            for (int ri = 0; ri < 6; ri++) {
                for (int rj = 0; rj < 6; rj++) {
                    if (stepArray[ri][rj] == 0) {
                        continue;
                    }
                    int sum = 0;
                    for (int tj = 0; tj < 6; tj++) {
                        if (ri == tj) {
                            continue;
                        }
                        sum += targetArray[rj][tj];
                        sum %= mod;
                    }
                    resultArray[ri][rj] = sum;
                }
            }
        }

        int result = 0;
        for (int[] line : resultArray) {
            for(int item : line) {
                result += item;
                result %= mod;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(new Solution2318().distinctSequences(1000));
        System.out.println(System.currentTimeMillis() - start);
    }
}